1550C - Manhattan Subarrays - CodeForces Solution

/*
 ▄████▄   █    ██  ██▀███    ██████ ▓█████ ▓█████▄     ███▄    █  ██▓ ███▄    █  ▄▄▄██▀▀▀▄▄▄
▒██▀ ▀█   ██  ▓██▒▓██ ▒ ██▒▒██    ▒ ▓█   ▀ ▒██▀ ██▌    ██ ▀█   █ ▓██▒ ██ ▀█   █    ▒██  ▒████▄
▒▓█    ▄ ▓██  ▒██░▓██ ░▄█ ▒░ ▓██▄   ▒███   ░██   █▌   ▓██  ▀█ ██▒▒██▒▓██  ▀█ ██▒   ░██  ▒██  ▀█▄
▒▓▓▄ ▄██▒▓▓█  ░██░▒██▀▀█▄    ▒   ██▒▒▓█  ▄ ░▓█▄   ▌   ▓██▒  ▐▌██▒░██░▓██▒  ▐▌██▒▓██▄██▓ ░██▄▄▄▄██
▒ ▓███▀ ░▒▒█████▓ ░██▓ ▒██▒▒██████▒▒░▒████▒░▒████▓    ▒██░   ▓██░░██░▒██░   ▓██░ ▓███▒   ▓█   ▓██▒
░ ░▒ ▒  ░░▒▓▒ ▒ ▒ ░ ▒▓ ░▒▓░▒ ▒▓▒ ▒ ░░░ ▒░ ░ ▒▒▓  ▒    ░ ▒░   ▒ ▒ ░▓  ░ ▒░   ▒ ▒  ▒▓▒▒░   ▒▒   ▓▒█░
  ░  ▒   ░░▒░ ░ ░   ░▒ ░ ▒░░ ░▒  ░ ░ ░ ░  ░ ░ ▒  ▒    ░ ░░   ░ ▒░ ▒ ░░ ░░   ░ ▒░ ▒ ░▒░    ▒   ▒▒ ░
░         ░░░ ░ ░   ░░   ░ ░  ░  ░     ░    ░ ░  ░       ░   ░ ░  ▒ ░   ░   ░ ░  ░ ░ ░    ░   ▒
░ ░         ░        ░           ░     ░  ░   ░                ░  ░           ░  ░   ░        ░  ░
░                                           ░
*/

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define ll long long int
#define INF int(1e9)
#define LINF 1e18

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

bool find(int a[], int l, int r)
{
	for (int i = l; i < r; i++)
	{
		for (int j = i + 1; j < r; j++)
		{
			for (int k = j + 1; k < r; k++)
			{
				if ((a[i] <= a[j] && a[j] <= a[k]) || (a[i] >= a[j] && a[j] >= a[k]))
				{
					return true;
				}
			}
		}
	}
	return false;
}

void solve(int tc)
{
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	ll ans = n + max(n - 1, 0) + max(n - 2, 0) + max(n - 3, 0);
	for (int i = 0; i <= n - 3; i++)
	{
		if (find(a, i, i + 3))
			ans--;
	}
	for (int i = 0; i <= n - 4; i++)
	{
		if (find(a, i, i + 4))
			ans--;
	}
	cout << ans << nl;
}

int main()
{
	// #ifndef ONLINE_JUDGE
	//     freopen("input.txt", "r", stdin);
	//     freopen("output.txt", "w", stdout);
	// #endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T = 1;
	cin >> T;
	for (int t = 1; t <= T; t++)
	{
		// cout << "Case #" << t << ": ";
		solve(t);
	}
}